Discovering Valuable Items from Massive Data

摘要

Suppose there is a large collection of items, each with an associated costand an inherent utility that is revealed only once we commit to selecting it.Given a budget on the cumulative cost of the selected items, how can we pick asubset of maximal value? This task generalizes several important problems suchas multi-arm bandits, active search and the knapsack problem. We present analgorithm, GP-Select, which utilizes prior knowledge about similarity be- tweenitems, expressed as a kernel function. GP-Select uses Gaussian processprediction to balance exploration (estimating the unknown value of items) andexploitation (selecting items of high value). We extend GP-Select to be able todiscover sets that simultaneously have high utility and are diverse. Ourpreference for diversity can be specified as an arbitrary monotone submodularfunction that quantifies the diminishing returns obtained when selectingsimilar items. Furthermore, we exploit the structure of the model updates toachieve an order of magnitude (up to 40X) speedup in our experiments withoutresorting to approximations. We provide strong guarantees on the performance ofGP-Select and apply it to three real-world case studies of industrialrelevance: (1) Refreshing a repository of prices in a Global DistributionSystem for the travel industry, (2) Identifying diverse, binding-affinepeptides in a vaccine de- sign task and (3) Maximizing clicks in a web-scalerecommender system by recommending items to users.